/**
 * 62. 不同路径
 * https://leetcode.cn/problems/unique-paths/description/
 */
class Solution {
    public int uniquePaths(int m, int n) {
        //动态规划
        int[][] dp = new int[m+1][n+1];
        dp[1][1] = 1;//初始化
        //填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == 1 && j == 1) continue;
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }
}

//局部变量，记忆化搜索
// class Solution {
//     public int uniquePaths(int m, int n) {
//         int[][] memory = new int[m+1][n+1];
//         return dfs(m, n, memory);
//     }
//     public int dfs(int i, int j, int[][] memory) {
//         if(memory[i][j] != 0) {
//             return memory[i][j];
//         }
//         if(i == 0 || j == 0) return 0;
//         if(i == 1 && j == 1) {
//             memory[i][j] = 1;
//             return 1;
//         }
//         if(memory[i][j] == 0) {
//             memory[i][j] = dfs(i - 1, j, memory) + dfs(i, j - 1, memory);
//         }
//         return memory[i][j];
//     }
// }

//全局变量，记忆化搜索
// class Solution {
//     int[][] memory;
//     public int uniquePaths(int m, int n) {
//         memory = new int[m+1][n+1];
//         return dfs(m, n);
//     }
//     public int dfs(int i, int j) {
//         if(memory[i][j] != 0) {
//             return memory[i][j];
//         }
//         if(i == 0 || j == 0) return 0;
//         if(i == 1 && j == 1) {
//             memory[i][j] = 1;
//             return 1;
//         }
//         if(memory[i][j] == 0) {
//             memory[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
//         }
//         return memory[i][j];
//     }
// }